﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Leetcode_Array.Script.DynamicProgramming
{
    class StockProblem
    {
        //==========================================力扣121 买卖股票的最佳时机
        //给定一个数组prices, 它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
        //你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
        //返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
        public int MaxProfit(int[] prices)
        {//贪心'
            int low = int.MaxValue;
            int result = 0;
            for (int i = 0; i < prices.Length; i++)
            {
                low = Math.Min(low, prices[i]);// 取最左最小价格
                result = Math.Max(result, prices[i] - low);// 直接取最大区间利润
            }
            return result;
        }

        public int MaxProfit_2(int[] prices)
        {//动态规划

            //dp[i][0] 表示第i天持有股票所得最多现金 (持有不代表当前买入，也可能是前一天买入）
            //dp[i][1] 表示第i天不持有股票所得最多现金
            int[,] pd = new int[prices.Length + 1, 2];
            pd[0, 0] -= prices[0];//
            pd[0, 1] = 0;//第0天不持有股票，则现金为0

            for (int i = 0; i < prices.Length; i++)
            {
                //当第i天持有股票：1）如果第i-1天就持有股票，则第i天的现金跟第i-1天持有的现金一致
                //               2）如果第i天才买入股票，则现金就是买入后所得的现金（假设第0天现金为0），即是-prices[i]
                pd[i, 0] = Math.Max(pd[i - 1, 0], -prices[i]);

                //当第i天不持有股票：1）如果第i-1天也不持有股票，则第i天的现金跟第i-1天持有的现金一致
                //2)如果第i天卖出股票，则现金为prices[i] + pd[i-1,0]
                pd[i, 1] = Math.Max(pd[i - 1, 1], prices[i] + pd[i - 1, 0]);
            }
            //本体中不持有股票时的金钱比持有股票多，所以是1.
            return pd[prices.Length - 1, 1];
        }

        //====================================================力扣122 买卖股票的最佳时机2
        //给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
        //设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
        //注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
        public int MaxProfit_3(int[] prices)
        {//贪心算法

            //局部最优：收集每天的正利润，全局最优：求得最大利润。
            int result = 0;
            for (int i = 1; i < prices.Length; i++)//第二天开始才有利润
            {
                result += Math.Max(prices[i] - prices[i - 1], 0);
            }
            return result;
        }

        public int MaxProfit_4(int[] prices)
        {
            //动态规划

            //dp[i][0] 表示第i天持有股票所得最多现金 (持有不代表当前买入，也可能是前一天买入）
            //dp[i][1] 表示第i天不持有股票所得最多现金
            int[,] dp = new int[prices.Length + 1, 2];
            dp[0, 0] -= prices[0];//
            dp[0, 1] = 0;//第0天不持有股票，则现金为0
            for(int i = 1;i<prices.Length;i++)
            {
                //当第i天持有股票：1）如果第i-1天就持有股票，则第i天的现金跟第i-1天持有的现金一致
                //               2）如果第i天才买入股票，则现金就是昨天不持有股票的现金减去今天股票的价格，即是pd[i-1,1] -prices[i]
                dp[i, 0] = Math.Max(dp[i - 1, 0], dp[i-1,1] -prices[i]);

                //当第i天不持有股票：1）如果第i-1天也不持有股票，则第i天的现金跟第i-1天持有的现金一致
                //2)如果第i天卖出股票，则现金为prices[i] + pd[i-1,0]
                dp[i, 1] = Math.Max(dp[i - 1, 1], prices[i] + dp[i - 1, 0]);
            }
            return dp[prices.Length - 1, 1];
        }

        //=============================================力扣123 买卖股票的最佳时机3
        //给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
        //设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易
        //注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
        public int MaxProfit_5(int[] prices)
        {
            //表示第i天状态j所剩最大现金
            //dp[i][1]，表示的是第i天，买入股票的状态，并不是说一定要第i天买入股票
            //0:没有操作，1：第一次买入，2：第一次卖出，3：第二次买入，4：第二次卖出
            int[,] dp = new int[prices.Length + 1, 5];

            dp[0, 0] = 0;
            dp[0, 1] = -prices[0];
            dp[0, 2] = 0;//
            dp[0, 3] = -prices[0];
            dp[0, 4] = 0;

            for(int i = 1;i<prices.Length;i++)
            {
                dp[i, 0] = dp[i - 1, 0];
                //第i天买入股票了，那么dp[i][1] = dp[i-1][0] - prices[i]
                //第i天没有操作，而是沿用前一天买入的状态，即：dp[i][1] = dp[i - 1][1]
                dp[i, 1] = Math.Max(dp[i - 1, 0] - prices[i], dp[i - 1, 1]);

                //第i天卖出股票了，那么dp[i][2] = dp[i - 1][1] + prices[i]
                //第i天没有操作，沿用前一天卖出股票的状态，即：dp[i][2] = dp[i - 1][2]
                dp[i, 2] = Math.Max(dp[i - 1, 1] + prices[i], dp[i - 1, 2]);

                //同上
                dp[i, 3] = Math.Max(dp[i - 1, 2] - prices[i], dp[i - 1, 3]);
                dp[i, 4] = Math.Max(dp[i - 1, 3] + prices[i], dp[i - 1, 4]);
            }
            return (dp[prices.Length - 1, 4]);
        }

        //=================================================力扣188 买卖股票的最佳时机4
        //给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。
        //设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
        //注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
        //0 <= k <= 100
        //0 <= prices.length <= 1000
        //0 <= prices[i] <= 1000
        public int MaxProfit_6(int k, int[] prices)
        {
            if (prices.Length == 0)
                return 0;

            //第i天的状态为j，所剩下的最大现金是dp[i][j]
            int[,] dp = new int[prices.Length, 2 * k + 1];
            //j的状态表示为：
            //0 表示不操作
            //1 第一次买入
            //2 第一次卖出
            //3 第二次买入
            //4 第二次卖出
            //所以除0外，偶数就是卖出，奇数就是买入
            
            for(int j = 1;j<2*k;j+=2)
            {
                dp[0, j] = -prices[0];
            }

            for(int i = 1;i<prices.Length;i++)
            {
                for (int j = 0; j < 2 * k - 1; j += 2) 
                {
                    dp[i, j + 1] = Math.Max(dp[i - 1, j] - prices[i], dp[i - 1, j + 1]);
                    dp[i, j + 2] = Math.Max(dp[i - 1, j+1] + prices[i], dp[i - 1, j + 2]);
                }
            }
            return dp[prices.Length - 1, 2 * k];
        }

        //============================================力扣309 最佳买卖股票时机含冷冻期
        //给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。​
        //设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
        //你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
        //卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
        public int MaxProfit_7(int[] prices)
        {
            if (prices.Length == 0)
                return 0;
            //第i天状态为j，所剩的最多现金为dp[i][j]。
            //状态一：买入股票状态（今天买入股票，或者是之前就买入了股票然后没有操作）
            //状态二：两天前就卖出了股票，度过了冷冻期，一直没操作，今天保持卖出股票状态
            //状态三：今天卖出了股票
            //状态四：今天为冷冻期状态，但冷冻期状态不可持续，只有一天！
            int[,] dp = new int[prices.Length , 4];

            dp[0, 0] = -prices[0];
            dp[0, 1] = 0;
            dp[0, 2] = 0;//最少收益就是0，绝不会是负数。
            dp[0, 3] = 0;

            for(int i = 1;i<prices.Length;i++)
            {
                //前一天就是持有股票状态（状态一），dp[i][0] = dp[i - 1][0]
                //今天买入了，有两种情况,前一天是冷冻期（状态四），dp[i - 1][3] - prices[i]
                //前一天是保持卖出股票状态（状态二），dp[i - 1][1] - prices[i]
                dp[i, 0] = Math.Max(dp[i - 1, 0], Math.Max(dp[i - 1, 3], dp[i - 1, 1]) - prices[i]);

                //前一天就是状态二
                //前一天是冷冻期（状态四）
                dp[i, 1] = Math.Max(dp[i - 1, 1], dp[i - 1, 3]);

                //昨天一定是买入股票状态（状态一），今天卖出
                dp[i, 2] = dp[i - 1, 0] + prices[i];

                //昨天卖出了股票（状态三）
                dp[i, 3] = dp[i - 1, 2];
            }

            return Math.Max(dp[prices.Length - 1, 3], Math.Max(dp[prices.Length - 1, 1], dp[prices.Length - 1, 2]));
        }

        //===========================================================力扣714 买卖股票的最佳时机含手续费
        //给定一个整数数组 prices，其中第 i 个元素代表了第 i 天的股票价格 ；整数 fee 代表了交易股票的手续费用。
        //你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
        //返回获得利润的最大值。
        //注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。
        public int MaxProfit_8(int[] prices, int fee)
        {
            int len = prices.Length;
            int[,] dp = new int[len, 2];
            dp[0, 0] = -prices[0];// 持股票
            for (int i = 1;i<len;i++)
            {
                dp[i, 0] = Math.Max(dp[i - 1, 0], dp[i - 1, 1] - prices[i]);
                dp[i, 1] = Math.Max(dp[i - 1, 1], dp[i - 1, 0] + prices[i] - fee);
            }
            return Math.Max(dp[len - 1, 0], dp[len - 1, 1]);
        }

    }
}
